"""
https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/description/

167. 两数之和 II - 输入有序数组
已解答
中等
相关标签
相关企业
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

 
示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
 

提示：

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 非递减顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案

"""

from typing import List, Tuple


class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        """
        常规思路-二分查找：
        从第1个数开始搜索其差second；差值从1~n-1范围内进行二分查找
        如果找到则成功，否则记录比second大的索引数max或略小的索引max-1；
        之后确定第2个数并从i=2~i=max-1之间通过二分查找，寻找second
        """
        # first_idx=0
        # first_val=numbers[first_idx]
        # second_val=target-first_val

        # second_idx按照左包右不包原则
        # second_start=first_idx+1
        second_end=len(numbers)

        def find_second_idx(val:int,start:int,end:int)->Tuple[int,int]:
            left=start
            right=end 

            while left+1<right:
                mid=(left+right)//2
                if val==numbers[mid]:
                    return (mid,None)
                elif val>numbers[mid]:
                    left=mid+1
                else:
                    right=mid
            
            if left<len(numbers) and val==numbers[left]:
                return (left,None)
            else:
                return (None,right)

        for first_idx in range(len(numbers)):
            first_val=numbers[first_idx]
            second_val=target-first_val

            second_start=first_idx+1
            second_idx,second_end=find_second_idx(second_val,second_start,second_end)
            if second_idx is not None:
                return [first_idx+1,second_idx+1]

        pass

if __name__=='__main__':
    s=Solution()
    numbers=[5,25,75]
    target=100
    res=s.twoSum(numbers,target)
    print(res)
    pass